///////
//
// Students: Aaron Lenard Hatcher and Russell James Lowke
//      T.F: Francis Crick & Bryan Kim
// Unit Nine, Design Document [worth 10pts],  8/7/2002
//


2.2.1 Understand Huffman algorithm (see hand drawn pages)

2.2.2 Make list of all classes and functions that you will use to create
	  Huffman trees.

Two classes will be used for building and manipulating Huffman trees.
These classes are Tree and Forest.

The Tree class constitutes the nodes on a Huffman Tree.
	Key properties are: letter, frequency, leftTree, rightTree.
	
The forest class is used for manipulating groups of Trees, and combining them
into a single key tree.  Encoding and Decoding is all resident within Forest,
and as such Forest is the common interface used by both Huff and Puff to the
Huffman Tree.


class Tree
{

	private:
	
 	  int	letter;							// letter this tree represents
	  int	frequency;						// frequency of this letter
	  Tree	*leftTree;						// ptr to left child (0)
	  Tree	*rightTree;						// ptr to right child (1)

	public:
        
	  // methods
	  Tree( int mFrequency, int mChar );	// constuctor used by class Forest
	  Tree( Tree  *mLeft, Tree  *mRight );	// constuctor used by merge()		
	  ~Tree();								// unnecessary destructor
	  void	setFrequency( int mFreqency );	// set the frequency for this tree
	  int	getFrequency();					// get the frequency
	  void	setLeft( Tree *mLeft );			// set left child
	  void	setRight( Tree *mRight );		// set right child
	  void	setLetter( char mChar );		// set Tree letter
	  int	getLetter();					// get Tree letter

};


class Forest
{
	private:
        
	  Tree 	*array[256];					// 256 letter frequency trees
	  Tree 	*key;							// finished tree from array[256]
	  code	encodings[256];					// list of binary encodings used
	  										// by Huff derived from key tree
                            
	  // methods
	  Tree 	*merge(Tree  *mLeft, Tree  *mRight);  // merges two tress into one
	  void 	sort();							// sorts forest of trees by frequency
            
	public:
        
	  // methods
	  Forest( int frequencyData[] );		// constructor
	  Tree 	*createKey();					// converts frequency data
	  										// into a single tree
	  void 	encode( Tree *keyTree );		// encode char to binary code
	  char 	decode( code mcode );			// decode binary code to to char
	  code	*getEncoding();					// return encoding array
	  										// ( used by Huff )
	  Tree	*getTree();						// return tree for decoding
	  										// ( used by Puff )
            

};

2.2.3 Linked lists and Binary Trees are the main data structures,
the binary trees being constructed from linked lists.
These trees (Huffman) will facilitate all of our encoding and decoding and
provide the information for encoding and decoding later.
Note: Once the main (key) Huffan Tree has been constructed, a table is made of
all the encodings for quick reference by Huff.

C++ definition: ( Class definition, see above )

Sentinel values:
NULL will be used to show that a tree has no children
-1 will be used to represent an interior tree node.

2.2.4 Show steps combining nodes (see hand drawn pages)

______


2.3.1 

 The class Forest (see above) will be used by both Huff and Puff
All methods within Forest are used by both, with the exception of:
decode() and getTree()  which is only used by Puff and
getEncoding()  which is only used by Huff.

The Huff class (see below) also has a method called compressToFile(), 
while the Puff class (see below) has a method called decompressToFile()

2.3.2 Duly noted.






2.3.3 Here are the two main classes that will be used in encoding and decoding
//
// compresses ASCII file to Huffman encoded binary
//
class Huff							
{
	private:
        
	  char		*inFile;			 		// name of ASCII file to read from
	  ifstream 	inStream;					// in stream for file
	  char		*outFile;			 		// name of BINARY file to write to
	  ofstream 	outStream;					// out stream for file
            
	  int		*table						// frequency array of 256 values
	  Forest	*forestKey					// key to forest class
            
 
	public:
        
	  // methods
	  bool	openFile( char *fileName );		// ensures file fileName (inFile)
	  void	frequencyTable();				// counts out a frequency table
	  										// from ascii file inFile
	  void	compressToFile( char *fileName );	// converts ascii to Huffman
	  										// encoded binary and saves to file			
}


//
// expand Huffman encoded binary file to ASCII
//
class Puff							
{
	private:
        
	char		*inFile;		 			// name of BINARY file to read from
	ifstream 	inStream;					// in stream for file
	char		*outFile;					// name of ASCII file to write to
	ofstream 	outStream;					// out stream for file
            
	int		*table							// frequency array of 256 values
	Forest 	*forestKey						// key to forest class
            
	public:
        
	// methods
	bool	openFile( char *fileName );		// ensures file fileName (inFile)
	void	frequencyTable();				// reads in a frequency table from
											// the header of file inFile
	void	decompressToFile( char *fileName );	// converts ascii to Huffman encoded
											// binary and saves to file
};



Forest::Forest ( int frequencyData[] );
	-This constructor will be used to make an instance of the class tree, and
	convert the array [frequencyData] into a new array of individual trees.
	
Tree	*Forest::createKey();
	-This method will transform the array of individual trees (a member variable of
	the Forest class) into one Huffman Tree.

Tree	*Forest::merge(Tree *mLeft, Tree *mRight);
	-This method will be used to link the lowest two trees together from the
	array of trees that is created in the constructor.
	
void Forest::sort();
	-This method of the tree class, once the array containing raw frequency data
	has been converted into trees, will be called to continually sort the trees
	into ascending order, as is necessary for merge() to work properly
	
code	*Forest::getEncoding();
	-return a handle to the array of encodings created within the 
	Tree class.  A method that will be called only by Huff.
	
Tree*	Forest::getTree();
	-return a handle to the root of the key tree for decoding.  A method that
	will be called only by Puff
	
void Huff::compressToFile( char *fileName );
	-this method uses the encodings returned by the Forest class to compress an
	ASCII file.
	
void Puff::decompressToFile( char *fileName );
	-this method uses the Huffman tree returned via forestKey to decode
	the encoded Huffman file back to ASCII;


2.3.4
Forest::Forest( int frequcneyData[] )
{
	for  all 256 characters in the frequency array, 
	{
		create a tree from the frequency data and put it in array[256] for later use;
	}
}

Tree	*Forest::createKey()
{
	while there is more than one tree in array[256]
	{
		sort() the rest of the list;
		merge() the lowest two into one tree;
	}
	return a pointer to the head tree;
}

Tree	*Forest::merge(Tree *mLeft, Tree *mRight)
{
	create a new tree with sentinal value -1 and a frequency equal to the sum of the
	two trees that are given as arguments;
	
	attach mLeft and mRight to the new node's left and right spots, respectively;

	return a pointer to the new node;
}

void	Forest::sort()
{
	sort items by frequency into ascending order;
	//Note: using the BUBBLESORT algorithm.  Not because we're lazy, but because
	//bubblesort is more efficient for lists that are nearly in order, as this one
	//will be for ALL passes except for the first.  We will need to go from the left
	//to right though, in order to ensure that only one class is necessary.
}

code	*Forest::getEncoding()
{
	return a pointer to the array of encoding information (encodings[256]);
}

Tree	*Forest::getTree()
{
	return a pointer to the root of the Huffman tree;
}

void	Huff::compressToFile( char *fileName )
{
	write array of frequencies into header;
	
	while not at end of file
	{
		get character from input file;
		lookup code for character;
		write code to output file;
	}
	get drunk, cheer wildly;
}



void	Puff::decompressToFile( char* fileName)
{
	read header from input file;
	build tree from header with forest;
	while not at end of the file
	{
		traverse tree using bits until we hit a leaf;
			(read bit, make appropriate "turn" in tree until at leaf)
		write character on leaf into output file;
	}
}

2.3.5

 Do the functions work well together? 				Yes
 is there duplication of code? 					No
 Does each function have one purpose? 				Yes
 Are you satisfied with your function hierarchy? 	Yes
 How could you improve it? 						Don't know yet.